/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // bfs
        TreeLinkNode *head, *tail;
        head=tail=root;
        while (head!=NULL) {
            if (head->left!=NULL) {
                tail->next=head->left;
                tail->next->next=head->right;
                tail=head->right;
            }
            head=head->next;
        }
        // set NULL
        head=root;
        for (int x=1;head!=NULL;x*=2) {
            for (int j=1;j<x;j++) head=head->next;
            TreeLinkNode *tmp=head->next;
            head->next=NULL;
            head=tmp;
        }
    }
};
